package com.likou;

/**
 * Author: 陈桂明
 * Date: 2025/4/8 22:13
 * Description: q34
 */
public class q34 {
    public int[] searchRange(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        int mid;

        if (high == -1) {
            return new int[]{-1, -1};
        }

        while (low <= high) {
            mid = (low + high) / 2;

            if (target <= nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 不存在
        if (low == nums.length) {
            return new int[]{-1, -1};
        }
        if (nums[high + 1] != target) {
            return new int[]{-1, -1};
        }

        // 存在
        int[] res = new int[2];
        res[0] = high + 1;
        for (int i = high + 1; i <= nums.length; i++) {
            if (i != nums.length) {
                if (nums[i] != target) {
                    res[1] = i - 1;
                    break;
                }
            } else {
                res[1] = i - 1;
            }
        }

        return res;
    }


    // 两次二分查找，分开查找第一个和最后一个
    // 时间复杂度 O(log n), 空间复杂度 O(1)
    // [1,2,3,3,3,3,4,5,9]
    public int[] searchRange2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int first = -1;
        int last = -1;
        // 找第一个等于target的位置
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                first = middle;
                right = middle - 1; // 重点
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        // 最后一个等于target的位置
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                last = middle;
                left = middle + 1; // 重点
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        return new int[]{first, last};
    }
}
